package com.wc.算法提高课.E第五章_数学知识.同余.同余方程;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * @Author congge
 * @Date 2024/10/9 13:13
 * @description https://www.acwing.com/problem/content/205/
 */
public class Main {
    /**
     * 背景知识<p>
     * 裴蜀定理：对于任意两个正整数 a, b ，一定存在非零 x, y 使得 ax + by = gcd(a, b)<p>
     * ax + by = d => by + (a % b)x = d => by + (a - a / b * b)x = d => ax + b(y - (a / b)x) = d <p>
     * b = 0 => x = 1, y = 0 是一组解。<p>
     * b > 0 => y = (y - (a / b) * x<p>
     * x = x + k * (b / d)
     * y = y + k * (a / d)
     * 思路：<p>
     * 由题意知道 ax == 1 (mod b) => ax + by = gcd(a, b)   <p>
     * x = (x % b + b) % b
     */
    static FastReader sc = new FastReader();
    static PrintWriter out = new PrintWriter(System.out);
    static long a, b;

    public static void main(String[] args) {
        a = sc.nextInt();
        b = sc.nextInt();
        long[] x = new long[1], y = new long[1];
        exgcd(a, b, x, y);
        out.println((x[0] % b + b) % b);
        out.flush();
    }

    static long exgcd(long a, long b, long[] x, long[] y) {
        if (b == 0) {
            x[0] = 1;
            y[0] = 0;
            return a;
        }
        long d = exgcd(b, a % b, y, x);
        y[0] -= a / b * x[0];
        return d;
    }
}

class FastReader {
    StringTokenizer st;
    BufferedReader br;

    FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    String nextLine() {
        String s = "";
        try {
            s = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return s;
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    // 是否由下一个
    boolean hasNext() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                String line = br.readLine();
                if (line == null)
                    return false;
                st = new StringTokenizer(line);
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return true;
    }
}
